package red.book._2._4;

import edu.princeton.cs.algs4.Inversions;

public class KendaIITau {
	// return Kendall tau distance between two permutations
    public static long distance(int[] a, int[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException("Array dimensions disagree");
        }
        int n = a.length;

        //保存了a中数据的位置关系， 比如a中的值为3索引是1， 所以这里保存的就是索引3的值为1.
        int[] ainv = new int[n];
        for (int i = 0; i < n; i++)
            ainv[a[i]] = i;

        Integer[] bnew = new Integer[n];
        for (int i = 0; i < n; i++)
            bnew[i] = ainv[b[i]];

        return Inversions.count(bnew);
    }

    public static void main(String[] args) {
        int[] a = new int[] { 0, 3, 1, 2 };
        int[] b = new int[] { 1, 0, 3, 2 };
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] + " " + b[i]);
        }
        System.out.println("Inversions:" + distance(a, b));
    }
}